package priv.pront.code.national.acwing.math;

import java.util.Scanner;

public class A868_筛素数 {
   /*普通筛log(n)*/
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] primes = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        int cnt = 0;
        for(int i=2;i<=n;i++){

            if(!st[i]) primes[cnt++]=i;//把素数存起来
            for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
                st[j]=true;
            }
        }

        /*线性筛 O（N）*/
//        Scanner scanner = new Scanner(System.in);
//        n = scanner.nextInt();
//        st = new boolean[n + 1];
//        prime = new int[n + 1];
//        for(int i = 2; i <= n; i++){
//            if(!st[i]) prime[cnt++] = i;
//            for(int j = 0; prime[j] <= n / i; j++){
//                st[prime[j] * i] = true;
//                if(i % prime[j] == 0) break;
//
//            }
//        }
//        System.out.println(cnt);


        /*埃式筛O（logn(logn)）*/
//        Scanner scanner = new Scanner(System.in);
//        n = scanner.nextInt();
//        st = new boolean[n + 1];
//        prime = new int[n + 1];
//        for(int i=2;i<=n;i++){
//            if(!st[i]){
//                prime[cnt++]=i;
//                for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
//            }
//        }
    }
}
